/*
 * @lc app=leetcode id=86 lang=cpp
 *
 * [86] Partition List
 */
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* partition(ListNode* head, int x) {

        if (!head || !head->next) {
            return head;
        }

        ListNode *fakeNode = new ListNode(-1);
        ListNode *node = fakeNode;
        fakeNode->next = head;

        ListNode *rightList = NULL;
        ListNode *rightNode = NULL;

        while (node->next) {
            if (node->next->val >= x) {
                ListNode *tmp = node->next;
                node->next = tmp->next;
                if (!rightList) {
                    rightList = tmp;
                    rightNode = tmp;
                } else {
                    rightNode->next = tmp;
                    rightNode = tmp;
                }
                rightNode->next = NULL;
            } else {
                node = node->next;
            }
        }

        node->next = rightList;
        head = fakeNode->next;
        delete fakeNode;
        return head;
    }
};

